package com.yiguang.algorithm.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DPTest {
	public static void main(String[] args) {
//		System.out.println(LocalDateTime.now());
//		System.out.println(getAllProbably(45));
//		System.out.println(LocalDateTime.now());
//		System.out.println(getAllProbably2(100));
//		System.out.println(LocalDateTime.now());
//		System.out.println(getAllProbably3(100));
//		System.out.println(LocalDateTime.now());
// 		System.out.println(nQueue(5));
		String[] wordDict = {"aa", "aabc", "cd", "cddaa"};
		System.out.println(wordBreak("aabccddaa", Arrays.asList(wordDict)));
	}

//	1 2 3 5 8 13
	public static Long getAllProbably(int n) {
		if(n==1) {
			return 1L;
		}
		if(n==2) {
			return 2L;
		}
		return getAllProbably(n-1)+getAllProbably(n-2);
	}
	
	private static List<Long> datas = new ArrayList();
	static {
		datas.add(0L);
		datas.add(1L);
		datas.add(2L);
	}
//	记忆化搜索
	public static Long getAllProbably2(int n) {
		if(datas.size()>n) {
			return datas.get(n);
		}
		datas.add(n, getAllProbably2(n-1)+getAllProbably2(n-2));
		return datas.get(n);
		
	}
//	动态规划
	public static Long getAllProbably3(int n) {
		Long[] datas = new Long[n+1];
		datas[1]=1L;
		datas[2]=2L;
		for(int i=3; i<=n; i++) {
			datas[i]=datas[i-1]+datas[i-2];
		}
		return datas[n];
	}
// 题型：斐波那契数列、跳楼梯每次只能跳一阶或者二阶
	
// N皇后
	public static List nQueue(int n) {
		List<List> result = new ArrayList();
		middle(result, n);
		return result;
	}
	
	private static void middle(List result, int n) {
		for(int x=0; x<n; x++) {
			List<List> data = new ArrayList(n);
			for(int y=0; y<n; y++) {
				List<String> curList = new ArrayList(n);
				for(int i=0; i<n; i++) {
					String cur = ".";
					curList.add(cur);
				}
				data.add(curList);
			}
			List<List> copyDate = data;
			middle2(result, copyDate, data, n, 0, x);
		}
	}
	
	private static boolean middle2(List result, List<List> copyDate, List<List> data, int n, int currentY, int currentX) {
		for(int y=currentY; y<n; y++) {
			List<String> curList = data.get(y);
			if(y==currentY) {
				while(curList.get(currentX)=="-1") {
					++currentX;
				}
				curList.set(currentX, "Q");
			}else {
				// 列 current
				// 反斜 x+1,y+1
				// 正斜 x-1,y+1
				curList.set(currentX, "-1");
				if(y-currentY+currentX<=n-1) {
					curList.set(y-currentY+currentX, "-1");
				}
				if(currentX-(y-currentY)>=0) {
					curList.set(currentX-(y-currentY), "-1");
				}
			}
			
		}
		System.out.println(data);
		List<List> copyData1 = data;
		List<String> curList = data.get(currentY+1);
		for(int i=0; i<curList.size(); i++) {
			if(curList.get(i)!="-1") {
				if(currentY+1==n-1) {
					System.out.println(currentY+1);
					curList.set(i, "Q");
					result.add(data);
					List<List> copyData = data;
					middle2(result, copyData, data, n, currentY-1, i+1);
				}else {
					System.out.println("再一次");
					List<List> copyData = data;
					if(middle2(result, copyData, data, n, currentY+1, i)) {
						
					}else {
						middle2(result, copyData, data, n, currentY, i+1);
					}
//					boolean curResult = middle2(result, data, n, currentY+1, i);
//					if(curResult==true)
//						middle2(result, data, n, currentY, currentX);
//					}
				}
			}
			if(i==n-1) {
				return false;
			}
		}
		return false;
	}
	
	/*
	给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
	注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

	示例 1：
	输入: s = "leetcode", wordDict = ["leet", "code"]
	输出: true
	解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
	
	示例 2：
	输入: s = "applepenapple", wordDict = ["apple", "pen"]
	输出: true
	解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
	     注意，你可以重复使用字典中的单词。
	
	示例 3：
	输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
	输出: false
	*/
	public static boolean wordBreak(String s, List<String> wordDict) {
		// aabccddaa
		// 0
		//1 1
		//   0
		//1   1
		//     0
		//    1 1
		//       0
		//        0
		//    1    1
		// aa aabc cd cddaa
		Set<String> words = new HashSet(wordDict);
		boolean[] dp = new boolean[s.length()+1];
		dp[0] = true;
		for(int i=1; i<=s.length(); i++) {
			for(int j=0; j<i; j++) {
				if(dp[j]==false) {
					continue;
				}
				if(dp[j]==true && words.contains(s.substring(j, i))) {
					dp[i] = true;
					break;
				}
			}
		}
		return dp[s.length()];
	}
}
